#ifndef __LOCK_FREE_LSIT__
#define __LOCK_FREE_LSIT__

#include "cpp_framework.h"
#include <memory>

using namespace CMDR;

template<typename T>
class LockFreeList {

	class Node : public HazardObject {
	public:
		const T								_item;
		AtomicMarkableReference<Node> _next;

		Node(const T& item) 
		: _item(item), _next(null, false) 
		{ }
		Node(const T& item, Node* const next, const bool mark) 
		: _item(item), _next(next, mark)
		{ }

		virtual ~Node() {
		}
	};

	Node _head;

public:

	LockFreeList() 
	: _head(Integer::MIN_VALUE, null, false)
	{
		Node* tail = new Node(Integer::MAX_VALUE);
		_head._next.set(tail,false);
	}

	bool add(const T& item) {
		while(true) {
			// find predecessor and current entries
			HazardPtr<Node> pred;
			HazardPtr<Node> curr;
			find(item, pred, curr);
			// is the key present?
			if (curr->_item == item) {
				return false;
			} else {
				// splice in new node
				std::auto_ptr<Node> node(new Node(item, curr.get() , false));
				if (pred->_next.compareAndSet(curr.get(), node.get(), false, false)) {
					node.release();
					return true;
				}
			}
		}
	}

	bool remove(const T& item) {
		while (true) {
			// find predecessor and current entries
			HazardPtr<Node> pred;
			HazardPtr<Node> curr;
			find(item, pred, curr);
			// is the key present?
			if (curr->_item != item) {
				return false;
			} else {
				// snip out matching node
				HazardPtr<Node> succ(curr->_next);
				const bool snip = curr->_next.attemptMark(succ.get(), true);
				if (!snip)
					continue;
				pred->_next.compareAndSet(curr.get(), succ.get(), false, false);
				return true;
			}
		}
	}
	bool contains(const T& item) {
		// find predecessor and current entries
		HazardPtr<Node> pred;
		HazardPtr<Node> curr;
		find(item, pred, curr);
		return (curr->_item == item);
	}

	void find(const T& item, HazardPtr<Node>& pred, HazardPtr<Node>& curr) {
		bool marked( false ); // is curr marked?
		HazardPtr<Node> succ; 

		while (true) {
			pred = _head;
			curr = pred->_next;

			while (true) {
				succ = curr->_next; 
				marked = curr->_next.isMarked();
				while (marked) {           // replace curr if marked
					const bool snip = pred->_next.compareAndSet(curr.get(), succ.get(), false, false);
					if (!snip) break;
					HazardMemory::retire_node(curr.get());
					Memory::read_write_barrier();
					curr = succ;
					succ = curr->_next;
					marked = curr->_next.isMarked();
				}
				if (curr->_item >= item) {
					return;
				}
				pred = curr;
				curr = succ;
			}
		}
	}
};

#endif
